package org.demo.algorithm;
/**
 * 计算排列数
 * @author  
 * @date    2010-12-22
 * @file    org.demo.algorithm.Permutation.java
 */
public class Permutation {
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {
		
		int[] data = new int[]{1,2,3,4,5,6,7,8,9};
		int[] used = new int[3];
		for (int i=0; i<used.length; i++){
			// 用 -1 来表示未使用
			used[i] = -1;
		}
		// 计算排列数
		calcPermutation(data, used, 0, 3);
	}
	/**
	 * 计算排列数
	 * @param data 原始数组
	 * @param used 存储一组解的下标
	 * @param level 当前层次 [0, deep]
	 * @param deep 排列深度 [level, min(used.length, data.length)]
	 */
	public static void calcPermutation(int[] data, int[] used,
			int level, int deep){
		if (level == deep){
			// 完成一组解
			output(data, used);
			return;
		}
		// 计算当前层的下一个可用值
		int next = getNext(used, level, data.length);
		while (next != -1){
			// 为当前层赋值
			used[level] = next;
			// 处理下一层
			calcPermutation(data, used, level + 1, deep);
			// 回溯时将下一层还原
			if (level + 1 < used.length){
				used[level + 1] = -1;
			}
			next = getNext(used, level, data.length);
		}
	}
	/**
	 * 获取下一个未使用的值
	 * @param used 存储一组解的下标
	 * @param level 当前层次 [0, used.length)
	 * @param length 
	 * @return
	 */
	private static int getNext(int[] used, int level, int length) {
		int result = -1;
		for (int i=used[level] + 1; i<length; i++){
			// 标记当前下标是否已经使用过
			boolean available = true;
			for (int j=0; j<=level; j++){
				if (i == used[j]){
					available = false;
					break;
				}
			}
			if (available){
				result = i;
				break;
			}
		}
		return result;
	}
	/**
	 * 输出一组解
	 * @param data
	 * @param used
	 */
	private static void output(int[] data, int[] used) {
		int result = 0;
		for (byte i=0; i<used.length; i++){
			result = result * 10 + data[used[i]];
		}
		System.out.println(result);
	}
}
